package com.ly.algorithm.DataStructures.sort;
import	java.util.Date;

import java.util.Random;

/**
 * @Classname RadixSort
 * @Description TODO
 * @Date 2020/4/24 21:03
 * @Author 冷心影翼
 */
public class RadixSort {

    public static void main(String[] args) {
//        int[] arr = {55,202,21,23,34,34,56,7,13,23,77,17};

        int[] arr = new int[800000];

        Random random = new Random();
        for(int i=0;i<800000;i++) {
            arr[i] =  random.nextInt(800000);
        }

        int[][] bucket = new int[10][arr.length];
        int[] countArr = new int [10];
        int maxLength = 5;

        Date date1 = new Date();
        for(int i=1;i<=maxLength;i++) {
            for (int j = 0; j < arr.length; j++) {
                String s = String.valueOf(arr[j]);
                int temp = 0;
                if(s.length()-i>0) {
                    temp = Integer.parseInt(s.substring(s.length()-i-1,s.length()-i));
                }
                bucket[temp][countArr[temp]++] = arr[j];
            }
            int index = 0;
            for(int j=0;j<10;j++) {
                if(countArr[j]!=0){
                    for (int k=0;k<countArr[j];k++) {
                        arr[index++] = bucket[j][k];
                    }
                }
                countArr[j] = 0;
            }
        }

        Date date2 = new Date();
        System.out.println(date2.getTime()-date1.getTime());
//        System.out.println(Arrays.toString(arr));
    }
}
